package dichotomyMethod;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author kunkun
 * @className LeetCode_32
 * @Description ...
 * @date 2025/3/18 11:21
 */
public class LeetCode_74 {

    @Test
    public void test(){
        System.out.println(searchMatrix(new int[][]{
                new int[]{-9, -7, -7, -7, -6, -6, -6, -4, -3, -1, 0},
                new int[]{3, 5, 6, 8, 8, 10, 12, 14, 14, 16, 17},
                new int[]{20, 22, 23, 23, 23, 23, 25, 25, 27, 28, 28}
        }, 10));
    }

    public boolean searchMatrix(int[][] matrix, int target) {

        Integer i = searchCol(matrix, target);
        if (i<0 ){
            int j = Arrays.binarySearch(matrix[0], target);
            return j>=0;
        }
        if (i>matrix.length-1){
            int j = Arrays.binarySearch(matrix[matrix.length-1], target);
            return j>=0;
        }
        if (matrix[i][0]==target){
            return true;
        }
        int j1 = Arrays.binarySearch(matrix[i], target);
        return j1>=0;

    }

    public Integer searchCol(int[][] col,int target){
        int i = 0,j = col.length-1;
        while (i<j){
            int mid = i+(j-i+1)/2;
            if (col[mid][0] == target){
                return mid;
            } else if (col[mid][0] < target) {
                i = mid;
            }else {
                j = mid-1;
            }
        }
        return i;
    }



}
